{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Maximum Nesting Depth of Two Valid Parentheses Strings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: maxDepthAfterSplit"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #有效括号的嵌套深度"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p><strong>有效括号字符串 </strong>定义：对于每个左括号，都能找到与之对应的右括号，反之亦然。详情参见题末「<strong>有效括号字符串</strong>」部分。</p>\n",
    "\n",
    "<p><strong>嵌套深度</strong> <code>depth</code> 定义：即有效括号字符串嵌套的层数，<code>depth(A)</code> 表示有效括号字符串 <code>A</code> 的嵌套深度。详情参见题末「<strong>嵌套深度</strong>」部分。</p>\n",
    "\n",
    "<p>有效括号字符串类型与对应的嵌套深度计算方法如下图所示：</p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/04/01/1111.png\" style=\"height: 152px; width: 600px;\"></p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p>给你一个「有效括号字符串」 <code>seq</code>，请你将其分成两个不相交的有效括号字符串，<code>A</code> 和&nbsp;<code>B</code>，并使这两个字符串的深度最小。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>不相交：每个 <code>seq[i]</code> 只能分给 <code>A</code> 和 <code>B</code> 二者中的一个，不能既属于 <code>A</code> 也属于 <code>B</code> 。</li>\n",
    "\t<li><code>A</code> 或 <code>B</code> 中的元素在原字符串中可以不连续。</li>\n",
    "\t<li><code>A.length + B.length = seq.length</code></li>\n",
    "\t<li>深度最小：<code>max(depth(A), depth(B))</code>&nbsp;的可能取值最小。&nbsp;</li>\n",
    "</ul>\n",
    "\n",
    "<p>划分方案用一个长度为 <code>seq.length</code> 的答案数组 <code>answer</code> 表示，编码规则如下：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>answer[i] = 0</code>，<code>seq[i]</code> 分给 <code>A</code> 。</li>\n",
    "\t<li><code>answer[i] = 1</code>，<code>seq[i]</code> 分给 <code>B</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果存在多个满足要求的答案，只需返回其中任意 <strong>一个 </strong>即可。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>seq = &quot;(()())&quot;\n",
    "<strong>输出：</strong>[0,1,1,1,1,0]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong>seq = &quot;()(())()&quot;\n",
    "<strong>输出：</strong>[0,0,0,1,1,0,1,1]\n",
    "<strong>解释：</strong>本示例答案不唯一。\n",
    "按此输出 A = &quot;()()&quot;, B = &quot;()()&quot;, max(depth(A), depth(B)) = 1，它们的深度最小。\n",
    "像 [1,1,1,0,0,1,1,1]，也是正确结果，其中 A = &quot;()()()&quot;, B = &quot;()&quot;, max(depth(A), depth(B)) = 1 。 \n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;&nbsp;seq.size &lt;= 10000</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>有效括号字符串：</strong></p>\n",
    "\n",
    "<pre>仅由&nbsp;<code>&quot;(&quot;</code> 和&nbsp;<code>&quot;)&quot;</code>&nbsp;构成的字符串，对于每个左括号，都能找到与之对应的右括号，反之亦然。\n",
    "下述几种情况同样属于有效括号字符串：\n",
    "\n",
    "  1. 空字符串\n",
    "  2. 连接，可以记作&nbsp;<code>AB</code>（<code>A</code> 与 <code>B</code> 连接），其中&nbsp;<code>A</code>&nbsp;和&nbsp;<code>B</code>&nbsp;都是有效括号字符串\n",
    "  3. 嵌套，可以记作&nbsp;<code>(A)</code>，其中&nbsp;<code>A</code>&nbsp;是有效括号字符串\n",
    "</pre>\n",
    "\n",
    "<p><strong>嵌套深度：</strong></p>\n",
    "\n",
    "<pre>类似地，我们可以定义任意有效括号字符串 <code>s</code> 的 <strong>嵌套深度</strong>&nbsp;<code>depth(S)</code>：\n",
    "\n",
    "  1.<code> s</code> 为空时，<code>depth(&quot;&quot;) = 0</code>\n",
    "<code>  2. s</code> 为 <code>A</code> 与 <code>B</code> 连接时，<code>depth(A + B) = max(depth(A), depth(B))</code>，其中&nbsp;<code>A</code> 和&nbsp;<code>B</code>&nbsp;都是有效括号字符串\n",
    "<code>  3. s</code> 为嵌套情况，<code>depth(&quot;(&quot; + A + &quot;)&quot;) = 1 + depth(A)</code>，其中 <code>A</code> 是有效括号字符串\n",
    "\n",
    "例如：<code>&quot;&quot;</code>，<code>&quot;()()&quot;</code>，和&nbsp;<code>&quot;()(()())&quot;</code>&nbsp;都是有效括号字符串，嵌套深度分别为 0，1，2，而&nbsp;<code>&quot;)(&quot;</code> 和&nbsp;<code>&quot;(()&quot;</code>&nbsp;都不是有效括号字符串。\n",
    "</pre>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [maximum-nesting-depth-of-two-valid-parentheses-strings](https://leetcode.cn/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [maximum-nesting-depth-of-two-valid-parentheses-strings](https://leetcode.cn/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(()())\"', '\"()(())()\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        #由判断括号字符串是否有效的栈的方式出发,栈中存左括号，栈高度就是深度，然后对半分\n",
    "        #但不用真正维护一个栈\n",
    "        ans=[]\n",
    "        depth=0\n",
    "        for c in seq:\n",
    "            if c=='(':\n",
    "                depth+=1#对应入栈操作，深度+1\n",
    "                ans.append(depth%2)\n",
    "            else:\n",
    "                # depth-=1#对应出栈操作，深度-1\n",
    "                ans.append(depth%2)#应该是与栈顶的左括号是一个组合\n",
    "                #因此-1操作应该在后面\n",
    "                depth-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:   \n",
    "        countA=0\n",
    "        countB=0\n",
    "        ans=[0]*len(seq)\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i]=='(':\n",
    "                if countA<countB:\n",
    "                    countA+=1\n",
    "                else:\n",
    "                    countB+=1\n",
    "                    ans[i]=1\n",
    "            else:\n",
    "                if countA<countB:\n",
    "                    countB-=1\n",
    "                    ans[i]=1\n",
    "                else:\n",
    "                    countA-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = list()\n",
    "        for i, ch in enumerate(seq):\n",
    "            if ch == '(':\n",
    "                ans.append(i % 2)\n",
    "            else:\n",
    "                ans.append(1 - i % 2)\n",
    "            # 上面的代码也可以简写成\n",
    "            # ans.append((i & 1) ^ (ch == '(')) \n",
    "            # C++ 和 Javascript 代码中直接给出了简写的方法\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        answer=[0]*len(seq)\n",
    "        for i in range(0,len(seq)-1):\n",
    "            if seq[i]==seq[i+1]:\n",
    "                answer[i+1]=abs(answer[i]-1)\n",
    "            else:\n",
    "                answer[i+1]=answer[i]\n",
    "        return answer\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res = [0]*len(seq)\n",
    "        for i in range(1, len(seq)):\n",
    "            if seq[i] == seq[i-1]: # 前后分到不同组\n",
    "                res[i] = 1 - res[i-1]\n",
    "            else:\n",
    "                res[i] = res[i-1] # 前后同组\n",
    "        return res\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res = [0]*len(seq)\n",
    "        stack = 0\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i] == '(':\n",
    "                stack += 1\n",
    "                res[i] = stack % 2\n",
    "            else:\n",
    "                res[i] = stack % 2\n",
    "                stack -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res = [0] * len(seq)\n",
    "        for i in range(1, len(seq)):\n",
    "            if seq[i] == seq[i-1]:\n",
    "                res[i] = 1 - res[i-1]\n",
    "            else:\n",
    "                res[i] = res[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        flag = True\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                if flag:\n",
    "                    ans.append(0)\n",
    "                    flag = not flag\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    flag = not flag\n",
    "            else:\n",
    "                if flag:\n",
    "                    ans.append(1)\n",
    "                    flag = not flag\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                    flag = not flag\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res = [0] * len(seq)\n",
    "        for i in range(1, len(seq)):\n",
    "            if seq[i] == seq[i-1]:\n",
    "                res[i] = 1 - res[i-1]\n",
    "            else:\n",
    "                res[i] = res[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        n = len(seq)\n",
    "        ans = [0] * n\n",
    "        cnt0,cnt1 = 0,0\n",
    "        for idx,c in enumerate(seq):\n",
    "            if c == '(':\n",
    "                if cnt0 < cnt1:\n",
    "                    cnt0 += 1\n",
    "                    ans[idx] = 0\n",
    "                else:\n",
    "                    cnt1 += 1\n",
    "                    ans[idx] = 1\n",
    "            else:\n",
    "                if cnt0 > cnt1:\n",
    "                    cnt0 -= 1\n",
    "                    ans[idx] = 0\n",
    "                else:\n",
    "                    cnt1 -= 1\n",
    "                    ans[idx] = 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/maximum-nesting-depth-of-two-valid-parentheses-strings/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ll = []\n",
    "        k = 0\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                k = k + 1\n",
    "                ll.append(k % 2)\n",
    "            else:\n",
    "                ll .append(k % 2)\n",
    "                k = k - 1\n",
    "        return ll"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "\n",
    "        res = [0]*len(seq)\n",
    "\n",
    "        for i in range(1, len(seq)):\n",
    "\n",
    "            if seq[i] == seq[i-1]: # 前后分到不同组\n",
    "\n",
    "                res[i] = 1 - res[i-1]\n",
    "\n",
    "            else:\n",
    "\n",
    "                res[i] = res[i-1] # 前后同组\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        flag = True\n",
    "        lag = True\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                if flag:\n",
    "                    ans.append(0)\n",
    "                    flag = not flag\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    flag = not flag\n",
    "            else:\n",
    "                if lag:\n",
    "                    ans.append(0)\n",
    "                    lag = not lag\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    lag = not lag\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, s: str) -> List[int]:\n",
    "        return [(i&1) ^ (s[i]=='(') for i in range(len(s))]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        temp = 0\n",
    "        ans = []\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                temp += 1\n",
    "                ans.append(temp & 1)\n",
    "            else:\n",
    "                ans.append(temp & 1)\n",
    "                temp -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d & 1)\n",
    "            else:\n",
    "                ans.append(d & 1)\n",
    "                d -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res = []\n",
    "        d = 0\n",
    "        for ch in seq:\n",
    "            if ch == '(':\n",
    "                d += 1\n",
    "                res.append(d % 2)\n",
    "            else:\n",
    "                res.append(d % 2)\n",
    "                d -= 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                ans.append(d%2)\n",
    "                d += 1\n",
    "            if c == ')':\n",
    "                d -= 1\n",
    "                ans.append(d%2)   \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        A=[]\n",
    "        La=0\n",
    "        B=[]\n",
    "        Lb=0\n",
    "        ans=[]\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i]==\"(\":\n",
    "                if La<Lb:\n",
    "                    ans.append(0)\n",
    "                    La+=1\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    Lb+=1\n",
    "            else:\n",
    "                if La<Lb:\n",
    "                    ans.append(1)\n",
    "                    Lb-=1\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                    La-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            else:\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\tdef maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "\t    temp = 0\n",
    "\t    ans = []\n",
    "\t    for i in seq:\n",
    "\t        if i == '(':\n",
    "\t            temp += 1\n",
    "\t            ans.append(temp & 1)\n",
    "\t        if i == ')':\n",
    "\t            ans.append(temp & 1)\n",
    "\t            temp -= 1\n",
    "\t    return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        isOne = False\n",
    "        s = []\n",
    "        res = []\n",
    "        for ch in seq:\n",
    "            if ch == \"(\":\n",
    "                res.append(len(s) % 2)\n",
    "                s.append(len(s) % 2)\n",
    "                \n",
    "            else:\n",
    "                res.append(s.pop())\n",
    "\n",
    "        return res\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        temp = 0\n",
    "        ans = []\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                temp += 1\n",
    "                ans.append(temp & 1)\n",
    "            if i == ')':\n",
    "                ans.append(temp & 1)\n",
    "                temp -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 只要在遍历过程中，我们保证栈内一半的括号属于序列 A，一半的括号属于序列 B，那么就能保证拆分后最大的嵌套深度最小，是当前最大嵌套深度的一半。\n",
    "# 要实现这样的对半分配，我们只需要把奇数层的 ( 分配给 A，偶数层的 ( 分配给 B 即可。\n",
    "# 对于上面的例子，我们将嵌套深度为 1 和 3 的所有括号 (()) 分配给 A，嵌套深度为 2 的所有括号 ()()() 分配给 B。\n",
    "\n",
    "# 此外，由于在这个问题中，栈中只会存放 (，因此我们不需要维护一个真正的栈，只需要用一个变量模拟记录栈的大小。\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        cur = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                cur += 1\n",
    "                ans.append(cur % 2) # 我们只需要把奇数层的 ( 分配给 A，偶数层的 ( 分配给 B 即可。\n",
    "            elif c == ')':\n",
    "                ans.append(cur % 2)\n",
    "                cur -= 1\n",
    "                \n",
    "        \n",
    "        return ans\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\r\n",
    "        ans = []\r\n",
    "        depth = 0\r\n",
    "        for c in seq:\r\n",
    "            if c == '(':\r\n",
    "                depth += 1\r\n",
    "                ans.append(depth % 2)\r\n",
    "            else:\r\n",
    "                ans.append(depth % 2)\r\n",
    "                depth -= 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res=[]\n",
    "        depth=0\n",
    "        for ch in seq:\n",
    "            if ch=='(':\n",
    "                depth+=1\n",
    "                res.append(depth%2)\n",
    "                \n",
    "            elif ch==')':\n",
    "                res.append(depth%2)\n",
    "                depth-=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        # A 或 B 中的元素在原字符串中可以不连续。\n",
    "        # 划分问题，背包问题？？？？，因为需要得到最后答案，所以，回溯or 贪心？？？栈？？\n",
    "        \n",
    "        n = len(seq)\n",
    "        \n",
    "        stack = []\n",
    "        ans = [0]*n\n",
    "        for i,x in enumerate(seq):\n",
    "            if x == '(':\n",
    "                stack.append(i)\n",
    "                ans[i] = len(stack)\n",
    "            else:\n",
    "                ans[i] = ans[stack.pop()]\n",
    "        # print(ans)\n",
    "                \n",
    "        for i,x in enumerate(ans):\n",
    "            ans[i] = ans[i]%2\n",
    "        return ans\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        res=[0]*len(seq)\n",
    "        for i in range(1,len(seq)):\n",
    "            if seq[i]==seq[i-1]:\n",
    "                res[i]=1-res[i-1]\n",
    "            else:\n",
    "                res[i]=res[i-1]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        # 思路：参考示例 “(()())”，遇到左括号嵌套深度就+1，左括号下一位如果是右括号，那它们是一对，嵌套深度相同，那我们可以按\n",
    "        # 嵌套深度的奇偶数来分组，然后将嵌套深度为奇数的位置记录1，为偶数的位置记录0.\n",
    "        depth = 0\n",
    "        res = []\n",
    "        for c in seq:\n",
    "            if c == '(': # 遇到左括号嵌套深度+1\n",
    "                depth += 1\n",
    "                res.append(depth&1) # 如果depth是奇数则&1的结果为1，为偶数则&1的结果为0，这里其实是一个奇偶数的判断技巧\n",
    "            else: # depth当前值就是当前右括号的嵌套深度\n",
    "                res.append(depth&1)\n",
    "                depth -= 1\n",
    "        return res\n",
    "                \n",
    "                \n",
    "            \n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        depth, tmp_depth = 0, 0\n",
    "        for i in seq:\n",
    "            if i == \"(\":\n",
    "                tmp_depth += 1\n",
    "                depth = max(depth, tmp_depth)\n",
    "            else:\n",
    "                tmp_depth -= 1\n",
    "        single_depth = depth // 2\n",
    "        result, tmp_depth = [], 0\n",
    "        for i in seq:\n",
    "            if i == \"(\":\n",
    "                tmp_depth += 1\n",
    "                result.append(1 if tmp_depth > single_depth else 0)\n",
    "            else:\n",
    "                result.append(1 if tmp_depth > single_depth else 0)\n",
    "                tmp_depth -= 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        La=0\n",
    "        Lb=0\n",
    "        ans=[]\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i]==\"(\":\n",
    "                if La<Lb:\n",
    "                    ans.append(0)\n",
    "                    La+=1\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    Lb+=1\n",
    "            else:\n",
    "                if La<Lb:\n",
    "                    ans.append(1)\n",
    "                    Lb-=1\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                    La-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        La=0\n",
    "        Lb=0\n",
    "        ans=[]\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i]==\"(\":\n",
    "                if La<Lb:\n",
    "                    ans.append(0)\n",
    "                    La+=1\n",
    "                else:\n",
    "                    ans.append(1)\n",
    "                    Lb+=1\n",
    "            else:\n",
    "                if La<Lb:\n",
    "                    ans.append(1)\n",
    "                    Lb-=1\n",
    "                else:\n",
    "                    ans.append(0)\n",
    "                    La-=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "                \n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "from typing import List\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        stack = deque([])\n",
    "        result = [None for _ in range(len(seq))]\n",
    "        k = 0\n",
    "        for i, v in enumerate(seq):\n",
    "            if v == '(':\n",
    "                k += 1\n",
    "                stack.append((i, k % 2))\n",
    "            elif v == ')':\n",
    "                k -= 1\n",
    "                left, no = stack.pop()\n",
    "                result[left] = result[i] = no\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        temp = 0\n",
    "        ans = []\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                temp += 1\n",
    "                ans.append(temp % 2)\n",
    "            if i == ')':\n",
    "                ans.append(temp % 2)\n",
    "                temp -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        st1, st2 = [], []\n",
    "        n = len(seq)\n",
    "        res = [-1] * n\n",
    "        for i in range(n):\n",
    "            c = seq[i]\n",
    "            if c == '(':\n",
    "                if len(st1) <= len(st2):\n",
    "                    st1.append(i)\n",
    "                    res[i] = 0\n",
    "                else:\n",
    "                    st2.append(i)\n",
    "                    res[i] = 1\n",
    "            elif c == ')':\n",
    "                if not st2 or ( st1 and st1[-1] > st2[-1]):\n",
    "                    st1.pop()\n",
    "                    res[i] = 0\n",
    "                else:\n",
    "                    st2.pop()\n",
    "                    res[i] = 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        n = len(seq)\n",
    "        res = [0]*n\n",
    "        s = []\n",
    "        for i,c in enumerate(seq):\n",
    "            if c == '(':\n",
    "                s.append(c)\n",
    "                if len(s)%2==0:\n",
    "                    res[i]=1\n",
    "            else:\n",
    "                if len(s)%2==0:\n",
    "                    res[i]=1\n",
    "                s.pop()\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        # 类似剥洋葱，这一层归你，下一层归我，得到每一层的编号，奇数编号一组，偶数编号一组。匹配的后括号的编号的与其前括号的编号\n",
    "        ans = []\n",
    "        d = 0\n",
    "        for c in seq:\n",
    "            if c == '(':\n",
    "                d += 1\n",
    "                ans.append(d % 2)\n",
    "            if c == ')':\n",
    "                ans.append(d % 2)\n",
    "                d -= 1\n",
    "        return ans\n",
    "        #直接在找编号的时候就就直接计算结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "\n",
    "        \"\"\"\n",
    "        字符串valid\n",
    "        任何时刻都有 l >= r\n",
    "\n",
    "        将每次栈迭代的最大深度拆成两份即可\n",
    "        \"\"\"\n",
    "        n = len(seq)\n",
    "        stack = []\n",
    "        group = [0]*n\n",
    "        switch = 1\n",
    "        depth = 0\n",
    "        for i, x in enumerate(seq):\n",
    "            if x == \"(\":\n",
    "                stack.append(i) \n",
    "                \n",
    "                # 深度增加时，switch才会换\n",
    "                if len(stack) > depth:\n",
    "                    switch ^= 1\n",
    "                    depth = len(stack)\n",
    "                \n",
    "                group[i] = switch\n",
    "                \n",
    "            else: \n",
    "                t = stack.pop(-1)\n",
    "                group[i] = group[t]\n",
    "                switch ^= 1\n",
    "                depth -= 1\n",
    "                \n",
    "        return group\n",
    "\n",
    "        # for i, x in enumerate(seq):\n",
    "        #     if x == \"(\":\n",
    "        #         stack.append(i) \n",
    "        #     else: \n",
    "        #         # 该弹出，注意当前深度, 至少一半的深度给外层\n",
    "        #         depth = len(stack)\n",
    "        #         g1 \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        q=[]\n",
    "        l,r=0,0\n",
    "        for x in seq:\n",
    "           if x=='(':\n",
    "              l+=1\n",
    "              if l%2:\n",
    "                 q.append(0)\n",
    "              else:\n",
    "                 q.append(1)      \n",
    "           else:\n",
    "              if l%2:\n",
    "                 q.append(0)\n",
    "              else:\n",
    "                 q.append(1)   \n",
    "              l-=1\n",
    "           \n",
    "           \n",
    "        return q                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        if seq==\"\":\n",
    "            return []\n",
    "        t=[]\n",
    "        depth=[]\n",
    "        mid=len(depth)//2\n",
    "        a_cnt=0\n",
    "        for x in seq:\n",
    "            if x==\"(\":\n",
    "                depth.append(\"(\")\n",
    "                mid=max(len(depth)//2,mid)\n",
    "                if a_cnt<mid:\n",
    "                    t.append(0)\n",
    "                    a_cnt+=1\n",
    "                else:\n",
    "                    t.append(1)\n",
    "            else:\n",
    "                depth.pop()\n",
    "                mid=max(len(depth)//2,mid)\n",
    "                if a_cnt>0:\n",
    "                    t.append(0)\n",
    "                    a_cnt-=1\n",
    "                else:\n",
    "                    t.append(1)\n",
    "        return t"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        # 类似剥洋葱，这一层归你，下一层归我，得到每一层的编号，奇数编号一组，偶数编号一组。匹配的后括号的编号的与其前括号的编号\n",
    "        n = len(seq) \n",
    "        stack = []\n",
    "        ans = [0]*n\n",
    "        for i,x in enumerate(seq):\n",
    "            if x == '(':\n",
    "                stack.append(i)\n",
    "                ans[i] = len(stack)\n",
    "            else:\n",
    "                ans[i] = ans[stack.pop()]\n",
    "        # print(ans)\n",
    "                \n",
    "        for i,x in enumerate(ans):\n",
    "            ans[i] = ans[i]%2\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        stack = []\n",
    "        deep = 0\n",
    "        res = []\n",
    "        for i in range(len(seq)):\n",
    "            if seq[i] == '(':\n",
    "                stack.append(seq[i])\n",
    "                deep += 1\n",
    "            else:\n",
    "                stack.pop()\n",
    "                deep -= 1\n",
    "            if (deep if seq[i] == '(' else deep + 1) & 1 == 1: res.append(1)\n",
    "            else: res.append(0)\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def maxDepthAfterSplit(self, seq: str) -> List[int]:\n",
    "        stk = []\n",
    "        d = 0\n",
    "        for i in seq:\n",
    "            if i == '(':\n",
    "                d += 1\n",
    "                stk.append(d %2)\n",
    "            elif i == ')':\n",
    "                stk.append(d %2)\n",
    "                d -= 1\n",
    "        return stk"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
